package th.retrofit.lib;

import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;

public class StringSolution {

    /**
     * 最长公共子序列
     * https://leetcode-cn.com/problems/longest-common-subsequence/
     * dp[i][j] 是以s1[i]和s2[j]为最后一个元素的公共子序列
     * @param text1 字符串 text1
     * @param text2 字符串 text2
     * @return 返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0
     */
    public int longestCommonSubsequence(String text1, String text2) {
        int len1 = text1.length();
        int len2 = text2.length();
        int[][] subLen = new int[len1 + 1][len2 + 1];
        for (int i = 0; i < len1; i++) {
            subLen[i][0] = 0;
        }
        for (int i = 0; i < len2; i++) {
            subLen[0][i] = 0;
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j ++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    subLen[i][j] = subLen[i - 1][j - 1] + 1;
                } else {
                    subLen[i][j] = Math.max(subLen[i - 1][j], subLen[i][j - 1]);
                }
            }
        }
        return subLen[len1][len2];
    }

    /**
     * https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/
     * 输入：s = "barfoothefoobarman", words = ["foo","bar"]
     * 输出：[0,9]
     * 解释：
     * 从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
     * 输出的顺序不重要, [9,0] 也是有效答案。
     * @param s 字符串
     * @param words 子串
     * @return 索引集合
     */
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if (s == null || s.length() == 0 || words == null || words.length == 0
        || s.length() < words.length * words[0].length()) return result;
        HashMap<String, Integer> dictionary = new HashMap<>();
        for (String word : words) {
            dictionary.put(word, dictionary.getOrDefault(word, 0) + 1);
        }
        int wordLen = words[0].length();
        int wordsLen = words.length;
        for (int i = 0; i <wordLen; i++) {
            int left = i, count = 0, right =i;
            HashMap<String, Integer> temp = new HashMap<>();
            while (right + wordLen <= s.length()) {
                String subWord = s.substring(right, right + wordLen);
                right += wordLen;
                if (!dictionary.containsKey(subWord)) {
                    left = right;
                    temp.clear();
                    count = 0;
                } else {
                    temp.put(subWord, temp.getOrDefault(subWord, 0) + 1);
                    count++;
                    while (temp.get(subWord) > dictionary.get(subWord)) {
                        String startWord = s.substring(left, left + wordLen);
                        temp.put(startWord, temp.get(startWord) - 1);
                        count--;
                        left = left + wordLen;
                    }
                    if (count == wordsLen) result.add(left);
                }
            }
        }
        return result;
    }

    /**
     * https://leetcode-cn.com/problems/longest-valid-parentheses/
     * 最长有效括号
     * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
     * @param s 只包含 '(' 和 ')' 的字符串
     * @return 最长有效括号的长度
     */
    public int longestValidParentheses(String s) {
        if (s == null) return 0;
        int length = s.length();
        if (length < 2 ) return 0;
        int cursor = 0, left = 0, right = 0, result = 0;
        while (cursor < length) {
            if (s.charAt(cursor++) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                result = Math.max(result, 2 * left);
            } else if (right> left){
                left = right = 0;
            }
        }
        left = right = 0;
        cursor = length - 1;
        while (cursor >= 0) {
            if (s.charAt(cursor--) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                result = Math.max(result, 2 * left);
            } else if (left > right){
                left = right = 0;
            }
        }
        return result;
    }

    /**
     * https://leetcode-cn.com/problems/longest-valid-parentheses/
     * 最长有效括号
     * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
     * @param s 只包含 '(' 和 ')' 的字符串
     * @return 最长有效括号的长度
     */
    public int longestValidParentheses1(String s) {
        int maxans = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    maxans = Math.max(maxans, i - stack.peek());
                }
            }
        }
        return maxans;
    }

    /**
     * https://leetcode-cn.com/problems/longest-valid-parentheses/
     * 最长有效括号
     * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
     * @param s 只包含 '(' 和 ')' 的字符串
     * @return 最长有效括号的长度
     */
    public int longestValidParentheses2(String s) {
        int sLen = s.length();
        int[] dp = new int[sLen];
        int result = 0;
        for (int i = 1; i < sLen; i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '('){
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1] - 2) >= 0 ? dp[i - dp[i - 1] - 2] : 0 ) + 2;
                }
                result = Math.max(result, dp[i]);
            }
        }
        return result;
    }

    /**
     * 最长公共子串
     * dp[i][j] 是以s1[i]和s2[j]为最后一个公共元素的公共子串
     * @param s1 字符串 text1
     * @param s2 字符串 text2
     * @return 返回这两个字符串的最长 公共串 的长度。如果不存在 公共子串，返回 0
     */
    public int longestCommonSubString(String s1, String s2) {
        int len1 = s1.length();
        int len2 = s2.length();
        int max = 0;
        int[][] dp = new int[len1 + 1][len2 + 1];
        for (int i = 0; i <= len1; i++) {
            dp[i][0] = 0;
        }
        for (int i = 0; i <= len2; i++) {
            dp[0][i] = 0;
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = 0;
                }
                max = Math.max(max, dp[i][j]);
            }
        }
        return max;
    }


    public static void main(String[] args) {
//        String s = "barfoofoobarthefoobarman";
//        String[] words = {"bar","foo","the"};
//        List<Integer> result = new StringSolution().findSubstring(s, words);
//        for (Integer integer : result) {
//            System.out.println(integer);
//        }


        String s = "()(())";
        System.out.println(new StringSolution().longestValidParentheses2(s));

        System.out.println(new StringSolution().longestCommonSubsequence("abcde", "ace"));
        System.out.println(new StringSolution().longestCommonSubString("abcde", "cde"));
    }

}
